package algos_dasgupta;

import java.util.HashMap;
import java.util.Map;

public class Knapsack {
	
	private int fill(Map<Integer, Integer> items, int W) {
		
		int[] K = new int[W+1];
		K[0] = 0;
		
		for(int w = 1; w <= W; w++) {
			for(int i = 1; i <= w; i++) {
				int p = items.get(i) == null ? 0 : items.get(i);
				K[w] = Math.max(K[w-i] + p, K[w]);
				
			}
		}
		
		return K[W];
	}
	
	public static void main(String[] args) {
		Map<Integer, Integer> items = new HashMap<Integer, Integer>();
		items.put(6, 30);
		items.put(3, 14);
		items.put(4, 16);
		items.put(2, 9);
		
		Knapsack ks = new Knapsack();
		int ans = ks.fill(items,  10);
		System.out.println(ans);
	}

	
}
